package top.hkyzf.study.datastructure.sparsearray;

/**
 * 稀疏数组（未保存本地）
 * @author 朱峰
 * @date 2020-12-17 13:28
 */
public class SparseArray {
    public static void main(String[] args) {
        // 1. 先定义一个原数组并赋值。

        // 定义一个11*11的数组
        int [][] chessArrayOld = new int[11][11];
        // 赋初始值
        chessArrayOld[1][2] = 1;
        chessArrayOld[2][3] = 2;
        chessArrayOld[4][5] = 3;
        chessArrayOld[8][8] = 8;
        chessArrayOld[2][9] = 12;
        // 打印原数组
        System.out.println("原始数组为：");
        printArray(chessArrayOld);


        // 2. 转换为稀疏数组

        // 定义变量储存原数组有效数字，即稀疏数组行数
        int count = 0;
        for(int i=0; i<chessArrayOld.length; i++) {
            for(int j=0; j<chessArrayOld[i].length; j++) {
                // 数字有效
                if(chessArrayOld[i][j] != 0) {
                    count++;
                }
            }
        }
        // 定义一个稀疏数组
        int [][] sparseArray = new int[count+1][3];
        // 赋值第一行
        sparseArray[0][0] = chessArrayOld.length;
        sparseArray[0][1] = chessArrayOld[0].length;
        sparseArray[0][2] = count;
        // 赋值后面几行
        count = 0;
        for(int i=0; i<chessArrayOld.length; i++) {
            for(int j=0; j<chessArrayOld[i].length; j++) {
                // 数字有效，储存在稀疏数组中
                if(chessArrayOld[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = chessArrayOld[i][j];
                }
            }
        }
        System.out.println("稀疏数组为：");
        printArray(sparseArray);


        // 3. 还原为原数组
        int [][] chessArrayNew = new int[sparseArray[0][0]][sparseArray[0][1]];
        for(int i=1; i<sparseArray.length; i++) {
            chessArrayNew[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        System.out.println("还原后的数组为：");
        printArray(chessArrayNew);

    }

    // 输出数组结果
    private static void printArray(int [][] arrays) {
        for(int i=0; i<arrays.length; i++) {
            for(int j=0; j<arrays[i].length; j++) {
                if(j == arrays[i].length-1) {
                    System.out.printf("%d", arrays[i][j]);
                } else {
                    System.out.printf("%d\t", arrays[i][j]);
                }
            }
            System.out.println();
        }
    }
}
